package 力扣.二分.三步切分法;

public class 搜索旋转排序数组II_81 {
    public boolean search(int[] nums, int target) {
        if (nums == null || nums.length == 0){
            return false;
        }
        int N = nums.length;
        int l = 0,r = N;
        while (l < r){
            int m = (l + ((r - l) >> 1));
            if (nums[l] == target || nums[m] == target || nums[r - 1] == target)
                return true;
            if (nums[l] == nums[m]){// [1,1,1,0,1]
                l++;//因为刚才判断了nums[l]不是目标值，所以可以直接扔掉！
                continue;
            }
            if (nums[l] < nums[m]){//中间节点在右线段
                if (nums[l] < target && nums[m] > target){
                    r = m;
                }else {
                    l = m + 1;
                }
            }else {//中间节点在左线段
                if (nums[m] < target && nums[r - 1] > target){
                    l = m + 1;
                }else {
                    r = m;
                }
            }
        }
        return false;
    }


    public boolean search2(int[] nums, int target) {
           if (nums == null || nums.length == 0){
               return false;
           }
           final  int N = nums.length;
           int l = 0 ,r = N - 1;
           while (l < r){
               if (nums[l] == target){
                   return true;
               }
               if (nums[r] == target){
                   return true;
               }
               int m = l + ((r - l) >> 1);
               if (nums[m] == target){
                   return true;
               }
               if (nums[m] == nums[l]){//不知道在哪个线段了 ，就直接加减左右边界呗！
                   r--;
//                   l++;//都行
                   continue;//必须重新开始
               }
               if (nums[m] > nums[l]){//左
                   if (nums[m] > target && target > nums[l]){
                       r = m;
                   }else {
                       l = m + 1;
                   }
               }else {
                   if (nums[m] < target && target < nums[r]){
                       l = m + 1;
                   }else {
                       r = m;
                   }
               }
           }
           return nums[l] == target;
    }
}
